package cn.com.mdx.sort.heapsort.sliderpuzzle;

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.MinPQ;
import edu.princeton.cs.algs4.StdOut;

import java.util.ArrayList;
import java.util.List;

/**
 * <p> 处理类
 *
 * @author ：huangy
 * @date ：Created in 2020/11/5 3:20 下午
 */
public class Solver {

    /**
     * 面板
     */
    private final Board initial;

    /**
     * 小数优先队列
     */
    private final MinPQ<Board> minPQ;

    /**
     * 解决步骤
     */
    List<Board> solutionBoards = new ArrayList<>();

    /**
     * @param initial 初始面板
     * @return 解决方案
     * @Author huangy
     * @description //TODO 构造解决方法
     * @date 9:47 上午 2020/11/9
     **/
    public Solver(Board initial) {
        this.initial = initial;
        minPQ = new MinPQ<>();
    }

    /**
     * @return boolean
     * @Author huangy false 否 true 是
     * @description //TODO 面板是否是可解决的面板
     * @date 10:45 上午 2020/11/6
     **/
    public boolean isSolvable() {
        return true;
    }

    /**
     * @return int
     * @Author huangy
     * @description //TODO 计算移动次数
     * @date 10:46 上午 2020/11/6
     **/
    public int moves() {
        if (isSolvable())
            return initial.manhattan();
        return -1;
    }

    /**
     * @return java.lang.Iterable<cn.com.mdx.sort.heapsort.sliderpuzzle.Board>
     * @Author huangy
     * @description //TODO 解决方法
     * @date 2:26 下午 2020/11/9
     **/
    public Iterable<Board> solution() {
        if (!isSolvable()) return null;
        minPQ.insert(initial);
        //组建游戏树
        getGameTree(initial.neighbors(), solutionBoards);
        return solutionBoards;
    }

    /**
     * @param neighbors      邻居节点
     * @param solutionBoards 解决队列
     * @Author huangy
     * @description //TODO 获取游戏树
     * @date 2:33 下午 2020/11/9
     **/
    private void getGameTree(Iterable<Board> neighbors, List<Board> solutionBoards) {
        solutionBoards.add(minPQ.delMin());
        neighbors.forEach(neighbor -> {
            if (!neighbor.isGoal() && !initial.equals(neighbor)) {
                minPQ.insert(neighbor);
                //将邻居节点加入到优先队列中
                getGameTree(neighbor.neighbors(), solutionBoards);
            }
            if (neighbor.isGoal()) {
                solutionBoards.add(neighbor);
            }
        });
    }

    public static void main(String[] args) {
        //从文件中创建初始面板
        In in = new In(args[0]);
        int n = in.readInt();
        Integer[][] tiles = new Integer[n][n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                tiles[i][j] = in.readInt();
        Board initial = new Board(tiles);
        //解决
        Solver solver = new Solver(initial);
        //通过标准输出打印解答结果
        if (!solver.isSolvable())
            StdOut.println("No solution possible");
        else {
            StdOut.println("Minimum number of moves = " + solver.moves());
            for (Board board : solver.solution())
                StdOut.println(board);
        }

    }

}
